package com.example.recursion;

/**
 * @Date 2022/7/9
 * @Created by Jonathan
 */
public class RobotWalk {


    public static void main(String[] args) {
        // 一共7个格子 从3到2 走3步 有多少种方案
        final int walk = walk(7, 2, 5, 3);
        System.out.println(walk);
    }

    /**
     * @param N    一共N步
     * @param cur  当前所在位置
     * @param rest 还剩余多少步
     * @param P    终点位置
     * @return
     */
    private static int walk(int N, int cur, int rest, int P) {
        // 还剩0步的时候 当前位置是在目标位置吗  是的话那就是一种方案
        if (rest == 0) {
            return cur == P ? 1 : 0;
        }

        // 当前在1位置 只能向右边
        if (cur == 1) {
            return walk(N, 2, rest - 1, P);
        }

        // 当前在N位置
        if (cur == N) {
            return walk(N, N - 1, rest - 1, P);
        }
        // 在中间位置的话 那么既可以向右边 又可以向左边
        return walk(N, cur + 1, rest - 1, P) +
                walk(N, cur - 1, rest - 1, P);


    }
}
